//
// Created by Administrator on 2021/4/24.
//

/*给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。


示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：

输入：nums = [9], target = 3
输出：0


提示：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    /**
     * 初始化 dp[0]=1;
    遍历 i 从 1 到 target，对于每个 i，进行如下操作：
    遍历数组 nums 中的每个元素 num，当 num≤i 时，将 dp[i−num] 的值加到dp[i]。
    最终得到 dp[target] 的值即为答案。
    **/
    int combinationSum4(vector<int> &nums, int target) {
        sort(nums.begin(), nums.end());
        vector<long> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < target + 1; ++i) {
            for (int &num : nums) {
                if (num <= i and dp[i - num] < INT_MAX - dp[i]) { // 注意溢出
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp.back();
    }
};


int main() {
    Solution sol;
//    vector<int> v1{1, 2, 3};
    vector<int> v1{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220,
                   230, 240, 250, 260, 270, 280, 290, 300, 310, 320, 330, 340, 350, 360, 370, 380, 390, 400, 410, 420,
                   430, 440, 450, 460, 470, 480, 490, 500, 510, 520, 530, 540, 550, 560, 570, 580, 590, 600, 610, 620,
                   630, 640, 650, 660, 670, 680, 690, 700, 710, 720, 730, 740, 750, 760, 770, 780, 790, 800, 810, 820,
                   830, 840, 850, 860, 870, 880, 890, 900, 910, 920, 930, 940, 950, 960, 970, 980, 990, 111};
    cout << sol.combinationSum4(v1, 999) << endl;
    return 0;
}